package com.graph;

/*
 * Taranjeet singh Bhatia
 * Code For Assignment # 4
 * MinSpanTreeAlgo.java class
 */

import java.awt.Point;

public class MinSpanTreeAlgo {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		// defining graph given in problem.
		GraphClass g1 = new GraphClass(8);
		g1.addEdge(0, 1, 4);
		g1.addEdge(0, 3, 6);
		g1.addEdge(0, 6, 16);
		g1.addEdge(1, 2, 24);
		g1.addEdge(3, 2, 23);
		g1.addEdge(3, 4, 5);
		g1.addEdge(3, 6, 8);
		g1.addEdge(6, 4, 10);
		g1.addEdge(4, 2, 18);
		g1.addEdge(4, 5, 11);
		g1.addEdge(4, 7, 14);
		g1.addEdge(6, 7, 21);
		g1.addEdge(7, 5, 7);
		g1.addEdge(5, 2, 9);

		// DepthFirstSearch g2 = new DepthFirstSearch(g1);

		for (int i = 0; i < 9; i++) { // this is because we have only 9 chords
										// in graph
			DepthFirstSearch g2 = new DepthFirstSearch(g1); // running DFS over
															// the graph.

			if (g2.nonTreeEdges.isEmpty()) {
				break; // MST is found
			}
			Point e = g2.nonTreeEdges.get(0); // / fetching first non-tree edge
			if (e == null)
				break; // MST is found.
			int u, v;
			if (e.x < e.y) {
				u = e.x;
				v = e.y;
			} else {
				u = e.y;
				v = e.x;
			}
			Point w = g2.find_max_weight_edge(u, v); // finding maximum weight
														// edge in cycle.
			Point e1 = g2.heaviest_edge(e, w); // comparing max weight edge and
												// non-tree edge
			g1.removeEdge(e1.x, e1.y); // removing the max weight edge
		}

	}

}
